package 复习.面试TOP101.栈堆队列;

import java.util.ArrayList;

public class 最小的K个数 {
    ArrayList<Integer> list = new ArrayList<>();

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(k > input.length || input == null) return list;
        heapSort(input,k);
        return list;
    }

    public void heapSort(int [] input, int k){
        for (int i = (input.length-2) / 2; i >= 0; i--) {
            shiftDown(input,i,input.length);
        }
        int end = input.length - 1;
        while (end > 0){
            swap(input,0,end);
            shiftDown(input,0,end--);
        }
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
    }

    public void shiftDown(int[] input,int parent,int size){
        int child = parent * 2 +1;

        while(child < size){
            if(child + 1 < size && input[child] < input[child + 1]) child += 1;

            if(input[parent] < input[child]){
                swap(input,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }

    public void swap(int[] input,int left,int right){
        int tmp = input[left];
        input[left] = input[right];
        input[right] = tmp;
    }
}

/*

import java.util.ArrayList;

public class Solution {
    public static void swap(int[] arr,int left,int right){
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    public static void shiftDown(int[] arr,int size,int parent){//size是边界，就是向下调整的最后一个可调整的节点的位置
        int child = parent * 2 + 1;
        while(child < size){
            if(child + 1 < size && arr[child + 1] > arr[child]){
                child += 1;
            }
            //接下来进行交换，并且
            if(arr[parent] < arr[child]){
                swap(arr,parent,child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }
        }
    }
    public static void heapSort(int[] arr){
        int size = arr.length;
        for(int root = (arr.length-2)/2; root >= 0; root--){
            shiftDown(arr, arr.length, root);
        }
        int end = size - 1;
        while(end != 0){
            swap(arr,0,end);
            shiftDown(arr,end,0);
            end--;
        }
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> myarr = new ArrayList<>();
        if(input.length == 0){
            return myarr;
        }
        heapSort(input);
        for (int i = 0; i < k; i++) {
            myarr.add(input[i]);
        }
        return myarr;
    }
}
 */